The LINUX NETWORK ARCHITECTUREchap16 IP Routing

The Internet Protocol V4: 

The Internet Protocol V4 2006. 11. 19 (일) 발표자 : 성 백 동 컴퓨터 네트워크 특강 seminar [The LINUX NETWORK ARCHITECTURE] : Klaus Wehrle 2005년

Contents: 

Contents Introduction Networks and Routers Forwarding and Routing IP Addresses Forwarding Procedure Routing Cache Rule-based Routing Configuration Configuring the Kernel File in the proc File system Configuration on System Level Implementation Routing Rules Routing Tables The Routing Cache The Forwaring Process

Introduction: 

Introduction One of the most important functions of the IP layer is to forward packets routing the determination of the route that packets will take across the Internet and the forwarding of packets towards their destination

Networks and Routers: 

Networks and Routers routers special nodes are used to link subnetworks integrated in all subnetworks that are connected in one place five local area network network layer abstracts from lower layer routers are used both to link local area networks and to connect local area networks to the Internet dedicated routing device

Forwarding and Routing: 

Forwarding and Routing Routers forward IP packets forwarding information - topological knowledge continually update the topology information and determine suitable routes new paths are added old ones fail or are overheaded the network topology in remote place changes routing determine forwarding information in each router function Routing methods to determine forwarding in each router determining the best routes Forwarding A router has to look up a database and make a decision for each packet that passes through this router on its way through the Internet

Forwarding and Routing (cont’): 

Forwarding and Routing (cont’) Forwaring is implemented in the Linux Kernel a task of the IP layer routing is handled on higher layers routing protocols build on top of transport-layer protocols routing daemons userspace processes running in Linux systems

IP address: 

IP address Classless Inter-Domain Routing(CIDR) notation 192.168.152.0/21 192.168.152.0/255.255.248.0

IP address (cont’): 

IP address (cont’) Routers have their own IP addresses, as do all network nodes in TCP/IP networks Figure 16-4 Assigning IP addresses to end systems and network interfaces in routers

Forwading Procedure: 

Forwading Procedure IP packet received over a network interface falls into one of three categories the packet is addressed the router not forwarded the packet is addressed an end system in a neighboring network directly the packet is addressed an end system in a remote network forwarding Routing Table

Forwading Procedure (cont’): 

Forwading Procedure (cont’) Longest Prefix selecting the entry with the longest prefix from all entries with matching prefixes more specific information in the routing table has priority over less specific information

Routing Cache: 

Routing Cache implementation should be efficient search for an entry with the longest matching prefix used frequently In Linux, all routing-table entries are sorted by prefix length searched successively by descending prefix length not always efficient, when the table includes many different prefixes routing cache to reduce the number of search processes stores the table entries used last uses a hashing method operates on the source address and destination address of packet to be forwarded

Rule-based Routing: 

Rule-based Routing policy routing set of rules is used to select which table should be used for what packets Rules a selector and a type selector chooses the packets to which the rule can be applied type determines what should happen with a packet when the selector matches rules are applied by priority values in ascending order use the TOS field or the iptables marking(fwmark) five types of rules unicast, blackhole, unreachable, prohibit and nat unicast - normal case blackhole, unreachable, prohibit - packet discard blackhole create no feedback unreachable - destination network is unreachable prohibit - communication is not permitted nat - used for static network-address translation

Rule-based Routing (cont’): 

Rule-based Routing (cont’) Default Setting main and default initially empty system administrator has to add entries when the system boots main - normal routing entries default - lower priority backup solution searched in this order when rule-based routing is disabled in the kernel configuration local fixed managed by the kernel include entries describing the addresses of local network interface initially empty

Configuration: 

Configuration the options available to configure routing in Linux. kernel configuration modify some routing parameters while the system is running. proc file system add entries to routing tables and rule lists. ip command

configuring the kernel: 

configuring the kernel CONFIG_NETLINK "Kernel/User netlink socket" activates the bidirectional netlink interface between the kernel and the user-address space PF_NETLINK implemented with datagram sockets of the new protocol family used to communicate with different kernel areas NETLINK_ROUTE protocol identifier available only provided that CONFIG_NETLINK is active CONFIG_RTNETLINK "Routing messages" Routing rules and routing tables can be modified by using sockets of the PF_NETLINK protocol family and the NETLINK_ROUTE "protocol." RT netlink interface is used in the ip configuration tool eavesdrop on changes made to routing tables by other processes.

configuring the kernel (cont’): 

configuring the kernel (cont’) CONFIG_IP_ADVANCED_ROUTER "IP: advanced router" no direct effect select a number of additional options can be used to obtain much more control over the routing procedure. CONFIG_NETLINK and CONFIG_RTNETLINK are activated automatically CONFIG_IP_MULTIPLE_TABLES "IP: policy routing" links the file fib_rules.o into the kernel and enables the rule-based routing the kernel creates two routing tables(local and main) and searches them in this order. available in connection with rule-based routing: CONFIG_IP_ROUTE_FWMARK "IP: use netfilter MARK value as routing key" fwmark CONFIG_NETFILTER has to be active CONFIG_IP_ROUTE_NAT "IP: fast network address translation" use special routing entries to translate addresses (NAT). ip_nat_dumb.o to be linked into the kernel.

configuring the kernel (cont’): 

configuring the kernel (cont’) CONFIG_IP_ROUTE_MULTIPATH "IP: equal cost multipath" one of these routes selected randomly. CONFIG_IP_ROUTE_TOS "IP: use TOS value as routing key" the value of the Differentiated Services Codepoint field from the IP packet header to be included in the routing decision. CONFIG_IP_ROUTE_VERBOSE "IP: verbose route monitoring" messages are written to the system log when certain error situations occur during the routing process caused by attackes or faulty configurations. CONFIG_IP_ROUTE_LARGE_TABLES "IP: large routing tables" size of tables is increased automatically

configuring the kernel (cont’): 

configuring the kernel (cont’) CONFIG_IP_MROUTE "IP: multicast routing" activates multicast routing and links the ipmr.o file into the kernel CONFIG_WAN_ROUTER "WAN router" no effect on the routing procedure allows to use a Linux computer as WAN router. CONFIG_NET_FASTROUTE "Fast switching" If the input and output interfaces of a forwarded packet are different, accelerate the copying processrequired in some cases by special hardware support directly from network card to network card fast copying CONFIG_NET_SCHED "QoS and/or fair queuing" options for traffic control routing rules and routing-table entries can be used to classify packets. CONFIG_NET_CLS ("Packet classifier API") , CONFIG_NET_CLS_ROUTE4 to be activated CONFIG_NET_CLS_ROUTE causes the data structures for routing rules and routing-table entries to be extended by an element required for classification.

configuring the kernel (cont’): 

configuring the kernel (cont’)

Files in the proc File System: 

Files in the proc File System the /proc/net Directory include files that reflect extensive routing-related data struct in the kernel to read statistics about the number of packets or bytes that used a specific route except

Files in the proc File System (cont’): 

Files in the proc File System (cont’) probe and modify either by reading from or writing to a file by using the system call _sysctl() and the sysctl command ip_forward - forwarding functionality set to one route subdirectory used by the kernel to manage the routing cache conf/device subdirectories include the same entry If the all entry or the entry of an interface is set to 1, “Martians”(illegal address value) are shown in the system log Reverse-Path Filtering

Configuration on System Level: 

Configuration on System Level ip command used to manipulate routing rules and routing tables the ip rule command Table 16-2 Parameters for ip rule add and ip rule delete Table16-1 variants of the ip command

Configuration on System Level (cont’): 

Configuration on System Level (cont’) the ip route command The most important parameters for ip route

Configuration on System Level (cont’): 

Configuration on System Level (cont’) Ip shows us our links Link – network device ip shows us our IP addresses

Configuration on System Level (cont’): 

Configuration on System Level (cont’)

Configuration on System Level (cont’): 

Configuration on System Level (cont’) local table Main table 새로운 Rule 생성

Implementation: 

Implementation ip_route_input() and ip_route_output() invoked when IP packets are handled to run routing-specific task routing rules and routing tables form forwarding-information-base(FIB) forwarding query FIB request - initiated by calling the fib_lookup() the implementation of routing rules is strongly encapsulated within the FIB

Routing Rules: 

Routing Rules rule-based routing uses a set of rules to decide searched for a suitable entry to forward a packet the rules are processed successively by ascending priority value until a decision can be made. fib_rules.c , ip_fib.h Data Structures fib_rule structures list contain three entries default_rule, main_rule, and local_rule

Slide29: 

used to regulate access to the list link pointer reference counter , free when this counter reaches a value of zero set to one by explicitly deleting the rule priority run if the rule’s selector matches the packet currently being processed additional attributes for action

Routing Rules: 

Routing Rules Data Structure

Initailization and Internal Functions: 

Initailization and Internal Functions fib_rules_init() invoked when the routing is initialized during system start, does not have to initialize the rules list rule list registers the callback function fib_rules_export() in the notification chain for state changes to network devices.

RT Netlink Interface: 

RT Netlink Interface represents the only way to manage routing rules the table inet_rtnetlink_table[] has pointers for the message types these function are invoked to handle the corresponding RT netlink messages

RT Netlink Interface (cont’): 

RT Netlink Interface (cont’) functions consists in converting between the data structures of RT netlink messages and the fib_rule structure

Slide38: 

when rules are polled(message type RTM_GETRULE)

Slide40: 

routing table id

Interface to Forwarding Functions: 

Interface to Forwarding Functions the rules database represents the access point to the FIB virtually fib_lookup() handles only a small part of the work involved

Slide45: 

used to limit the search range

Slide46: 

serves to select a route from several default route select

Interface to Forwarding Functions (cont’): 

Interface to Forwarding Functions (cont’) access specific elements of the fib_rule structure fib_rules_tclass() - return the queuing discipline’s class identifier assigned to a rule fib_rules_policy() - transforms the source address as specified by a rule fib_rules_map_destination() - transforms the destination address for NAT routes

Interface to Forwarding Functions (cont’): 

Interface to Forwarding Functions (cont’)

Routing Table: 

Routing Table routing table are represented by rather complex data structures, which manage entries by using a number of hash tables for different prefix lengths Data Structures fib_table structure forms the basic for a routing table includes a pointer to an fn_zone structure for each potential prefix length (0~32bits) fn_zone structure uses an additional hash table to store the individual entries, each represented by a fib_node structure fn_zone structure manages all entries with the same prefix length by use of a hash table fib_node structure fib_info structure represent information about the result of an FIB query, including the output interface to be used and the next hop along the route to the destination system

Slide50: 

fixed prefix length used to mask the hash value to the range permitted for indexing in the array in its last computation step Prefix lengths

Slide51: 

set to functions in fib_hash.c

Slide52: 

the only way to access internal routing table data structures

Managing Hash Structure: 

Managing Hash Structure the functions access fn_zone and fib_node structure fn_rehash_zone() - enlarges the hash tables fn_new_zone() - create a new fn_zone structure and sorts it fn_hash_lookup() - handles the main task in an FIB query fn_hash_select_default() - selects one out of several default routes fn_hash_insert() , fn_hash_delete() , fn_hash_dump() - over the RT netlink interface fn_hash_flush() - removes all fib_info structure of a zone fn_hash_get_info() - display routing table entries over the proc file system

Interface to the User-Address Space: 

Interface to the User-Address Space manage routing tables both over the traditional ioctl() interface and over RT netlink invoked to add, delete, output a routing table entry and handle corresponding messages inet_rtm_newroute() inet_rtm_delroute() inet_rtm_dump_fib() ioctl() system handled by ip_rt_ioctl()handles

Slide60: 

the parameters converted into an RT netlink message

proc File System: 

proc File System /proc/net/route create by the function fib_get_procinfo() creates a header line and uses the function pointer tb_get_info() from the main table to output the data. registred by ip_fib_init() using proc_net_create() all fib_node structures in fn_zone_list are visited and the appropriate data is eventually output by fib_node_get_info()

Reacting to Changes in Network Interfaces: 

Reacting to Changes in Network Interfaces fib_inetaddr_event() and fib_netdev_event() registered in two notification chains for state changes to network interfaces or changes to their IP addresses when ip_fib_init() initializes the FIB fib_add_ifaddr() creates entries for local and broadcast routes in the local table fib_del_ifaddr() entries are deleted

Slide64: 

creates entries for local and broadcast routes in the local table

Interface to the Forwarding Functions: 

Interface to the Forwarding Functions fib_validate_source() check the source addresses of IP packets within a forwarding process fib_select_multipath() When a routing-table entry with several routes is used in a forwarding process invoked to select one of these routers made randomly , taking weights assigned to each of these routes into account ip_dev_find() inet_addr_type()

Slide66: 

FIB query validation is completed successfully acceptable result when reverse-path filtering is active if the actual input device does not currently have an address

The Routing Cache: 

The Routing Cache routing cache is based on a relatively simple data structure one single hash table includes the cache entries

Interface to Forwarding Function: 

Interface to Forwarding Function hardly encapsulated against the other program logic used for forwarding : route.c IP packet processing ( ip_route_input() and ip_route_output())

Slide71: 

The forwarding function use the rt_intern_hash() function to insert an almost complete rtable structure into the hash table of the routing cache

Slide73: 

allocates memory for the routing cache array rtable structure is initialized

Slide74: 

initialization functions of the IP interface management FIB are invoked the timer for cache garbage collection is started proc entries are created

Cache Garbage Collection: 

Cache Garbage Collection a timer called rt_periodic_timer initailly started by add_timer() this timer is restarted in rt_check_expire() ip_rt_gc_interval rt_garbage_collect() is invoked to delete old entries deleting cache entries is similar to that of rt_check_expire()

RT Netlink Interface: 

RT Netlink Interface Routing-cache entries can be read via the RT netlink interface messages are created by ip_rt_dump() invoked by inet_dump_fib() when cache entries are requested RT netlink message is processed by inet_rtm_getroute() registered in the table inet_rtnetlink_table[]

The Proc File System: 

The Proc File System some configuration variables - include to control the behavior of the cache garbage collection mapped to files in the /proc/sys/net/ipv4/route directory flush - causes the routing cache to be deleted when it is accessed ipv4_sysctl_rtcache_flush() handle access to the flush file /proc/net/rt_cache read the content of the entire routing cache formatted by the function rt_cache_get_info registered using proc_net_create()

Implementing the Internet Protocol: 

Implementing the Internet Protocol

The Forwading Process: 

The Forwading Process ip_route_input() invoked for each IP packet arriving over a network interface ip_route_input_mc() destination address is a multicast address multicast group or configured for multicast routing ip_route_input_slow()

Slide83: 

determine the route of a packet route cache routing table matching

Slide84: 

ip_route_input() continue dst addr이 multicast address인 경우 IPv4 specific data IP를 위한 설정된 네트워크 디바이스를 create Major route resolver routine

Slide85: 

rt_key structure is filled with the parameter check for invalid values

Slide86: 

FIB query is started by calling fib_lookup() NAT so , transforms the source address according to the information

Slide88: 

output() gets the ip_rt_bug()

Slide89: 

choose a route

Slide90: 

dev->ip_ptr을 얻어온다 src의 유효성 검사